package org.aplombh.java.leetcode.all;

public class _29两数相除 {
    public static void main(String[] args) {
        System.out.println(new Solution29_3().divide(10, 3));
    }
}

// 暴力
class Solution29_1 {
    public int divide(int dividend, int divisor) {

        if (dividend == 0) {
            return 0;
        }

        if (dividend == Integer.MIN_VALUE) {
            if (divisor == 1) {
                return Integer.MIN_VALUE;
            }
            if (divisor == -1) {
                return Integer.MAX_VALUE;
            }
        }

        if (divisor == Integer.MIN_VALUE) {
            return dividend == Integer.MIN_VALUE ? 1 : 0;
        }

        if (divisor == 1)
            return dividend;

        int flag = 1;

        if (dividend > 0) {
            flag = -flag;
            dividend = -dividend;
        }

        if (divisor > 0) {
            flag = -flag;
            divisor = -divisor;
        }


        int ans = 0;

        while (dividend <= divisor) {
            ans++;
            dividend -= divisor;
        }

        if (flag != 1)
            ans = -ans;

        return ans;
    }
}

// 暴力优化
class Solution29_2 {
    public int divide(int dividend, int divisor) {

        if (dividend == 0) {
            return 0;
        }

        if (dividend == Integer.MIN_VALUE) {
            if (divisor == 1) {
                return Integer.MIN_VALUE;
            }
            if (divisor == -1) {
                return Integer.MAX_VALUE;
            }
        }

        if (divisor == Integer.MIN_VALUE) {
            return dividend == Integer.MIN_VALUE ? 1 : 0;
        }

        if (divisor == 1)
            return dividend;

        int flag = 1;

        if (dividend > 0) {
            flag = -flag;
            dividend = -dividend;
        }

        if (divisor > 0) {
            flag = -flag;
            divisor = -divisor;
        }


        int[] power = new int[32];
        power[0] = divisor;

        int i;

        for (i = 1; i < 32; i++) {
            if (power[i - 1] < -1073741824)
                break;
            power[i] = power[i - 1] + power[i - 1];
        }


        int ans = 0;

        for (int j = i - 1; j >= 0; j--) {
            if (dividend <= power[j]) {
                dividend -= power[j];
                ans += 1 << j;
            }
        }

        if (flag != 1)
            ans = -ans;

        return ans;
    }
}

// 加减交替法
//① 被除数与除数同号，被除数减去除数；被除数与除数异号，被除数加上除数
//② 余数和除数同号，商为1，余数左移一位，下次减除数；余数和除数异号，商为0，余数左移一位，下次加除数。
//③ 重复步骤2，包括符号在内，工作n+1步

// TODO
class Solution29_3 {
    public int divide(int dividend, int divisor) {

        if (dividend == 0) {
            return 0;
        }

        if (dividend == Integer.MIN_VALUE) {
            if (divisor == 1) {
                return Integer.MIN_VALUE;
            }
            if (divisor == -1) {
                return Integer.MAX_VALUE;
            }
        }

        if (divisor == Integer.MIN_VALUE) {
            return dividend == Integer.MIN_VALUE ? 1 : 0;
        }

        if (divisor == 1)
            return dividend;


        int ans = 0;
        int y;
        if ((dividend & divisor) < 0)
            y = dividend + divisor;
        else
            y = dividend - divisor;

        for (int i = 1; i < 32; i++) {

            if ((y & divisor) > 0) {
                ans = (ans << 1) + 1;
                y = (y << 1) - divisor;
            } else {
                ans = (ans << 1);
                y = (y << 1) + divisor;
            }

        }
        return ans;
    }
}